def mergeSort(lst, low, high):
    if high - low < 2:
        return

    mid = (low + high) // 2

    mergeSort(lst, low, mid)
    mergeSort(lst, mid, high)
    merge(lst, low, mid, high)

def merge(lst, low, mid, high):
    print(low, high)
    i = low
    j = mid
    lstm = []
    while i < mid and j < high:
        if lst[i] < lst[j]:
            lstm.append(lst[i])
            i += 1
        else:
            lstm.append(lst[j])
            j += 1
    
    while i < mid:
        lstm.append(lst[i])
        i += 1
 
    while j < high:
        lstm.append(lst[j])
        j += 1

    # example:
    # a = [1, 3, 5, 7, 9, 10]
    # b = [2, 4, 6]
    # a[2: 5] = b
    # a -> [1, 3, 2, 4, 6, 10]
    lst[low: high] = lstm

a = [8, 4, 5, 7, 1, 3, 6, 2]
mergeSort(a, 0, len(a))
print(a)
